package 链表算法题;

public class 环型链表 {

    public class ListNode{
        int val;
        ListNode next;

        ListNode(int val){
            this.val = val;
        }
    }
    //其实用到了一些数学公式 但是不想详细去想了 随缘根据根据写了
    //就是他的依据就是判断有环的时候是让fast走两格 slow走一格 这样如果有环的话他们一定会相遇的
    /*然后如果有环的话 从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点，
    那么当这两个指针相遇的时候就是 环形入口的节点*/
    public ListNode huanxing(ListNode head){
        //判断是否有环
        ListNode slow = head;
        ListNode fast = head;
        while (fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast){//有环
                ListNode index1 = fast;
                ListNode index2 = head;
                while (index1!=index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}
